//https://leetcode.cn/problems/sqrtx/
#include <iostream>
#include <vector>

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        if(x==1) return 1;
        int l=0;
        int r=x;
        int res=0;
        while(l<r){
            int mid=(l+r)/2;
            if((long long)mid*mid<x){
                res=mid;
                l=mid+1;
            }else if((long long)mid*mid==x){
                res=mid;
                break;
            }else {
                r=mid;
            }
        }
        return res; 
    }
};